#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> combine(int n, int k)
    {
        _combine(1, n, k);
        return _ans;
    }

private:
    void _combine(int cur, int n, int k)
    {
        if (k == 0)
        {
            _ans.push_back(_v);
            return;
        }

        for (int i = cur; i <= n - k + 1; ++i)
        {
            _v.push_back(i);
            _combine(i + 1, n, k - 1);
            _v.pop_back();
        }
    }

private:
    vector<vector<int>> _ans;
    vector<int> _v;
};